package slidewindow;

import java.util.HashMap;
import java.util.Map;

public class 最小覆盖子串_76 {
    public String minWindow(String s, String t) {
        // 重点1 使用单个map来表示是否全部包含  
        // 窗口加一个字符对应 -1   窗口减一个字符 对应字符 +1
        Map<Character, Integer> charsCount = new HashMap<>();
        int left = 0, right = 0, minLength = Integer.MAX_VALUE, minLengthStart = s.length();
        for(Character c : t.toCharArray()) {
            charsCount.put(c, charsCount.getOrDefault(c, 0) + 1) ;
        }
        // 每次右移一个  
        while(right< s.length()) {
            char rightChar = s.charAt(right);
            if(charsCount.containsKey(rightChar)){
                charsCount.put(rightChar, charsCount.getOrDefault(rightChar, 0) - 1) ;
            }
            //  判断是否全包含  全包含则移动窗口左边界 进入缩小的循环
            while (check(charsCount)) {
               if(right - left < minLength) {
                   minLength = right -left;
                   minLengthStart = left;
               }
                char leftChar = s.charAt(left);
                if(charsCount.containsKey(leftChar)){
                    charsCount.put(leftChar, charsCount.getOrDefault(leftChar, 0) + 1) ;
                }
                left ++;
            }
            right ++;
        }

        if(minLength == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(minLengthStart, minLengthStart+minLength+1);
    }
    public boolean check(Map<Character, Integer> map) {
        for (int value : map.values()) {
            //注意这里的value是可以为负数的，为负数的情况就是，相同的字符右
            // 指针扫描的要比t中的多，比如t是"ABC"，窗口中的字符是"ABBC"
            if (value > 0)
                return false;
        }
        return true;
    }
}
